1. Field of the Invention
The present invention relates to 3-Dimensional (3D) mesh data imaging and, more particularly, to an apparatus and method for extending a Quadric Error Metrics (QEM) algorithm by discrete curvature for simplifying 3D mesh data.
2. Description of the Related Art
With the recent progress of advanced automation and development into information society, applications of computer graphic have increased rapidly, e.g., animation, simulation, etc. Amid this, the recent introduction of 3-Dimensional (3D) graphic techniques into electronic equipments leads to paying attention to the development of a high speed graphic processing technology for processing large numbers of polygons and efficiently processing special effects, such as lighting effects, in order to configure a little more realistic graphic.
Mesh simplification is a technique to retain the original desired shape and feature of a 3D model while reducing the number of polygons necessary to render the shape and features. That is, mesh simplification refers a process of removing polygons having topological and geometrical information more than needed from an initial model, thus simplifying the initial model. A technology for simplifying such a 3D model has been utilized in many fields such as a Level of Detail (LOD) control technology of a computer animation and 3D game, a 3D graphic solution of the Internet, a real-time 3D graphic simulation, etc.
A goal of mesh simplification is to provide good approximation to retain geometrical information on the original model and a phase with less vertex and face. An advantage of mesh simplification is to reduce the amount of storage space required for rendering a large size model, reduce a data-structure building time, and visualize a model at high speed.
A conventional simplification algorithm can give rise to a change of a volume of the original mesh model during the simplification process. Performance of the mesh simplification algorithm depends on an execution time for simplifying the original mesh model and a quality of approximation of the simplified model. Thus, a volume of a simplified mesh model has been considered using a distance based QEM algorithm of several simplification algorithms that uses the sum of squares of distances from one point on a plane providing relatively good performance.
The QEM algorithm is an algorithm for simplifying a mesh model using iterative edge contraction in which a method of selecting an edge to contract is of importance. The QEM algorithm determines a vertex whose distance error is minimal at each edge as a position of a new vertex after edge contraction, using a cost function of prioritizing an edge to contract (i.e., so-called QEM), first selects an edge at which the vertex has the least distance error among edges, and contracts the selected edge.
However, the QEM algorithm performs quick and high quality simplification, but there is a problem that it cannot keep a feature of the original 3D model when completing a simplification step of simplifying the original 3D model.